/**
 * 
 */
package Verifier.ArithmeticSystem;

import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.IntBuffer;
import java.util.Random;

import Verifier.ByteTree.ByteTree;
import Verifier.Cryptography.HashFunction;
import Verifier.Cryptography.PRG;

/**
 * Represents a modular group G_q where q is a prime which indicates the order of the group.
 * 
 * @author Moshe Baavur
 *
 */
public class ModularGroup extends Group {
	// represents the major group's creator
	private BigInteger groupCreator;
	// represents this modular group's order
	private BigInteger groupOrder;
	// represents the containing group's order
	private BigInteger containerGroupOrder;
	// the encoding scheme of the group
	private GroupEncodingScheme encodingScheme;
	// groups modding difference
	private BigInteger modDiff;
	// an element representing the creator of the group
	private ModularGroupElement creatorElement;
	
	/**
	 * Creates a modular group with the passed number as its order.
	 * 
	 * @param containerGroupOrder The order of the modular group which is the container of this group. This number cannot be zero or negative, and should be prime.
	 * @param groupOrder The order of the created group. This number cannot be zero or negative, and should be prime.
	 * @param groupCreator The group's creator. This number cannot be zero or negative, and should be of the order of groupOrder.
	 * @param encodingScheme The encoding scheme which is how to encode a message into and out of the group. Detailed description can be found in the verifier's documentation.
	 * @throws Exception containerGroupOrder or groupOrder or groupCreator are zero or negative, or if the encoding scheme doesn't match the specification, or if
	 * 					   the orders are not prime.
	 */
	public ModularGroup(BigInteger containerGroupOrder, BigInteger groupOrder, BigInteger groupCreator, int encodingScheme) throws Exception {
		// check that the order of the containing group is a positive number
		if (1 != containerGroupOrder.signum()) {
			throw new Exception("Modular Group: The order of the containing group cannot be zero or negative!");
		}
		// check that the order of the group is a positive number
		if (1 != groupOrder.signum()) {
			throw new Exception("Modular Group: The order of the group cannot be zero or negative!");
		}
		// check that the order of the group creator is a positive number
		if (1 != groupCreator.signum()) {
			throw new Exception("Modular Group: The order of the group creator cannot be zero or negative!");
		}
		
		this.modDiff = BigInteger.ZERO;
		
		// check that the order and the container order are probably prime
		if (false == containerGroupOrder.isProbablePrime(Verifier.Verifier.NumberOfPrimeTests)) {
			throw new Exception("Modular Group: The order of the containing group is not prime!");
		}
		
		if (false == groupOrder.isProbablePrime(Verifier.Verifier.NumberOfPrimeTests)) {
			throw new Exception("Modular Group: The order of the group is not prime!");
		}
		
		// need to check the encoding scheme
		switch (encodingScheme) {
			case 0:
				// no limitations for e = 0
				break;
			case 1:
				// check that p=2q+1
				BigInteger twoQ = BigInteger.valueOf(2).multiply(groupOrder);
				BigInteger pMinusOne = containerGroupOrder.subtract(BigInteger.ONE);
				
				if (!twoQ.equals(pMinusOne)) {
					// this is an error
					throw new Exception("Modular Group: The encoding scheme cannot be 1 if p<>2q+1 !");
				}
				break;
			case 2:
				// check that p=tq+1
				if (!BigInteger.ONE.equals(containerGroupOrder.mod(groupOrder))) {
					// this is an error
					throw new Exception("Modular Group: The encoding scheme cannot be 1 if p<>2q+1 !");
				}
				// now check that the bit length difference between p and q is less than 2^10
				int bitLengthDiff = containerGroupOrder.bitLength() - groupOrder.bitLength();
				if (1024 >= bitLengthDiff) {
					// this is an error
					throw new Exception("Modular Group: The encoding scheme cannot be 2 and the difference between the bit lengths of p and q is more than 2^10 !");
				}
				
				// calculate t for faster encoding
				this.modDiff = containerGroupOrder.subtract(BigInteger.ONE).divide(groupOrder);
				break;
			default:
				// this encoding scheme is unsupported
				throw new Exception("Modular Group: The encoding scheme " + encodingScheme + " is unsupported !");
		}
		
		// all the parameters are correct - save them
		this.groupCreator = groupCreator;
		this.containerGroupOrder = containerGroupOrder;
		this.groupOrder = groupOrder;
		this.encodingScheme = GroupEncodingScheme.ConvertFromInt(encodingScheme);
		
		// check that the creator is in the group
		this.creatorElement = null;
		try {
			// check that the creator is in the group and create an element of it on the way
			this.creatorElement = new ModularGroupElement(groupCreator, this);
		} catch (Exception e) {
			// an exception shouldn't be thrown - the creator should always be in the container group
			// we should throw an exception
			throw new Exception("Modular Group: The group creator is not in the container group!");
		}
	}
	
	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#getOrder()
	 */
	@Override
	public BigInteger getOrder() {
		return (groupOrder);
	}
	
	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#getContainingGroupOrder()
	 */
	@Override
	public BigInteger getContainingGroupOrder() {
		return (containerGroupOrder);
	}
	
	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#getGroupCreator()
	 */
	@Override
	public BigInteger getGroupCreator() {
		return (groupCreator);
	}
	
	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#getGroupCreatorAsGroupElement()
	 */
	@Override
	public ModularGroupElement getGroupCreatorAsGroupElement() {
		return (creatorElement);
	}
	
	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#getEncodingScheme()
	 */
	@Override
	public int getEncodingScheme() {
		return (encodingScheme.getValue());
	}
	
	/*
	 * Checks if the specified element is in the field, meaning the element is a non-negative number and lower than the field order. 
	 * 
	 * @param element - the element to check.
	 * @return true if and only if the element is a non-negative number which is lower than the field order. 
	 */
	private boolean doesElementBelong(BigInteger elementNumber)
	{
		// we are assuming that the orders p & q are prime and that g is an actual generator of the group

		// we check that a element belongs to the group using the formula : e^q=1 mod p
		 
		// if the element is negative
		if (-1 == elementNumber.signum())
			return (false);
		
		// now, calculate the mod-power
		BigInteger res = elementNumber.modPow(groupOrder, containerGroupOrder);
		
		// check that the result is 1 
		return (res.equals(BigInteger.ONE));
	}
	
	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#doesElementBelong(Verifier.ArithmeticSystem.GroupElement)
	 */
	@Override
	public boolean doesElementBelong(GroupElement element)
	{
		// if the element is of different type, we can't check it
		if (!(element instanceof ModularGroupElement)) {
			return (false);
		}
		
		// we are assuming that the orders p & q are prime and that g is an actual generator of the group

		// we check that a element belongs to the group using the formula : e^q=1 mod p
		return (doesElementBelong( ((ModularGroupElement)element).getElement()));
	}
	
	@Override
	public boolean equals(Object obj) {
		// if the object is a modular group, then compare them using their order and containing groups and not the address
		if (obj instanceof ModularGroup) {
			return (super.equals(obj));
		}
		// otherwise, they are not equal
		return (false);
	}
	
	// this method is used to encode a message into the group if the encoding scheme is 0
	private ModularGroupElement encodeType0(byte[] message, int maxNumBytes) {
		ModularGroupElement newElement = null;
		// do as the algorithm suggests:
		BigInteger r;
		Random rnd = new Random();
		boolean elemFound = false;
		
		do {
			// randomize a number
		    r = new BigInteger(groupOrder.bitLength(), rnd);
		    // create a new element of the form g^r
		    newElement = (ModularGroupElement) creatorElement.power(r);
		    // check if the new element fits to our data
		    byte[] result;
			try {
				result = HashFunction.SHA256.HashDigest(ArithmeticConvertor.ToByteTree(newElement));
			    // check that the message is there
			    elemFound = true;
			    for (int i = 0 ; i < message.length; i++) {
			    	if (message[i] != result[1 + i]) {
			    		elemFound = false;
			    		break;
			    	}
			    }
			    // now check the first byte
			    if (true == elemFound) {
			    	elemFound = ((result[0] % 4) == message.length);
			    }
			} catch (Exception e) {
				// an exception shouldn't be thrown, because the element has been built by us.
			}
		} while (!elemFound);

		return (newElement);
	}
	
	// this method is used to encode a message into the group if the encoding scheme is 1
	private ModularGroupElement encodeType1(byte[] message, int maxNumBytes) {
		ModularGroupElement newElement = null;
		// do as the algorithm suggests:
		// create a new message in the length of max number of bytes - and initialize it to 0
		byte[] newMessage = new byte[4 + maxNumBytes];
		
		// convert the size of the array into bytes
		ByteBuffer byteBuffer = ByteBuffer.allocate(4); // 4 = the number of bytes in a single int        
	    IntBuffer intBuffer = byteBuffer.asIntBuffer();
	    intBuffer.put(message.length);
	    byte[] lengtharray = byteBuffer.array();
		
		// copy the length first
		System.arraycopy(lengtharray, 0, newMessage, 0, lengtharray.length);
		// now comes the message
		if (0 == message.length) {
			// no message to encode - put the identity element
			newMessage[4] = 1;
		} else {
			System.arraycopy(message, 0, newMessage, 4, message.length);
		}
		
		// now look at the bytes as a number
		BigInteger newNumber = new BigInteger(newMessage);
		try {
			if (doesElementBelong(newNumber)) {
				newElement = (new ModularGroupElement(newNumber, this));
			} else {
				newElement = (new ModularGroupElement(containerGroupOrder.subtract(newNumber), this));
			}
		} catch (Exception e) {
			// no exception should be thrown if we done everything right
			return (null);
		}
		
		return (newElement);
	}
	
	// this method is used to encode a message into the group if the encoding scheme is 2
	private ModularGroupElement encodeType2(byte[] message, int maxNumBytes) {
		ModularGroupElement newElement = null;
		// do as the algorithm suggests:
		// create a new message in the length of max number of bytes + 4 bytes for the length of the message - and initialize it to 0
		byte[] newMessage = new byte[4 + maxNumBytes];
		// convert the size of the array into bytes
		ByteBuffer byteBuffer = ByteBuffer.allocate(4); // 4 = the number of bytes in a single int        
	    IntBuffer intBuffer = byteBuffer.asIntBuffer();
	    intBuffer.put(message.length);
	    byte[] lengtharray = byteBuffer.array();
		// copy the length first
		System.arraycopy(lengtharray, 0, newMessage, 0, lengtharray.length);
		// now comes the message
		System.arraycopy(message, 0, newMessage, 4, message.length);
		
		// now look at the bytes as a number
		BigInteger numberK = new BigInteger(newMessage);
		try {
			BigInteger valueToAdd = BigInteger.valueOf(2).pow(8*(maxNumBytes + 4));
			while (!doesElementBelong(numberK)) {
				numberK = numberK.add(valueToAdd);
				if (-1 != numberK.compareTo(containerGroupOrder)) {
					// we have a problem k got out of the scope of the group
					return (null);
				}
			}
			
			newElement = (new ModularGroupElement(numberK, this));
		} catch (Exception e) {
			// no exception should be thrown if we done everything right
			return (null);
		}
		
		return (newElement);
	}
	
	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#encode(byte[])
	 */
	@Override
	public ModularGroupElement encode(byte[] message) throws Exception {
		int maxNumBytes = encodingScheme.maxNumberOfEncodableBytes(containerGroupOrder.bitLength(), modDiff);
		if (maxNumBytes >= message.length) {
				throw new Exception("The encoding type does not allow the encoding of a message that long");
		}
		
		switch (encodingScheme) {
			case ENCODING_SCHEME_0:
				return (encodeType0(message, maxNumBytes));
			case ENCODING_SCHEME_1:
				return (encodeType1(message, maxNumBytes));
			case ENCODING_SCHEME_2:
				return (encodeType2(message, maxNumBytes));
		}
		
		return (null);
	}
	
	// this method is used to decode an item in the group to a message if the encoding scheme is 0
	private byte[] decodeType0(ModularGroupElement message, int maxNumBytes) {
		// first, hash the byte tree of message
		ByteTree messageTree;
		try {
			messageTree = ArithmeticConvertor.ToByteTree(message);
		} catch (Exception e) {
			// can't convert the message to byte tree
			return (new byte[0]);
		}
		// need to create SHA-256
		HashFunction hash = HashFunction.SHA256;
		
		byte[] hashedMessage = hash.HashDigest(ByteTree.byteStringToByteArray(messageTree.toString()));
		
		int messageLength = hashedMessage[0] % 4;
		
		byte[] decodedMessage = new byte[messageLength];
		System.arraycopy(hashedMessage, 1, decodedMessage, 0, messageLength);
		
		return (decodedMessage);
	}
	
	// this method is used to decode an item in the group to a message if the encoding scheme is 1
	private byte[] decodeType1(ModularGroupElement message, int maxNumBytes) {
		// k is the minimum between a and p-a where a is the message
		BigInteger numberK = message.getElement().min(containerGroupOrder.subtract(message.getElement()));
		
		// this is k mod 2^8*(b+4)
		BigInteger messageNumber = numberK.mod(BigInteger.valueOf(2).pow(8*(maxNumBytes + 4)));
		// convert this number to bytes
		byte[] messageBytesSmall = messageNumber.toByteArray();

		// the array might not be large enough - expand it by copying it to the end of a larger array
		byte[] messageBytes = new byte[maxNumBytes + 4];
		System.arraycopy(messageBytesSmall, 4, messageBytes, maxNumBytes + 4 - messageBytesSmall.length, messageBytesSmall.length);
		
		ByteBuffer bb = ByteBuffer.wrap(messageBytes, 0, 4);
		int messageLength = bb.getInt();
		
		if ((messageLength < 0) || (messageLength > maxNumBytes)) {
			messageLength = 0;
		}
		
		byte[] decodedMessage = new byte[messageLength];
		System.arraycopy(messageBytes, 4, decodedMessage, 0, messageLength);
		
		return (decodedMessage);
	}
	
	// this method is used to decode an item in the group to a message if the encoding scheme is 2
	private byte[] decodeType2(ModularGroupElement message, int maxNumBytes) {		
		// this is message mod 2^8*(b+4)
		BigInteger messageNumber = message.getElement().mod(BigInteger.valueOf(2).pow(8*(maxNumBytes + 4)));
		// convert this number to bytes
		byte[] messageBytesSmall = messageNumber.toByteArray();

		// the array might not be large enough - expand it by copying it to the end of a larger array
		byte[] messageBytes = new byte[maxNumBytes + 4];
		System.arraycopy(messageBytesSmall, 4, messageBytes, maxNumBytes + 4 - messageBytesSmall.length, messageBytesSmall.length);
		
		ByteBuffer bb = ByteBuffer.wrap(messageBytes, 0, 4);
		int messageLength = bb.getInt();
		
		if ((messageLength < 0) || (messageLength > maxNumBytes)) {
			messageLength = 0;
		}
		
		byte[] decodedMessage = new byte[messageLength];
		System.arraycopy(messageBytes, 4, decodedMessage, 0, messageLength);
		
		return (decodedMessage);
	}
	
	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#decode(Verifier.ArithmeticSystem.GroupElement)
	 */
	@Override
	public byte[] decode(GroupElement message) {
		int maxNumBytes = encodingScheme.maxNumberOfEncodableBytes(containerGroupOrder.bitLength(), modDiff);
		
		if (!(message instanceof ModularGroupElement)) {
			return (null);
		}
		
		switch (encodingScheme) {
			case ENCODING_SCHEME_0:
				return (decodeType0((ModularGroupElement)message, maxNumBytes));
			case ENCODING_SCHEME_1:
				return (decodeType1((ModularGroupElement)message, maxNumBytes));
			case ENCODING_SCHEME_2:
				return (decodeType2((ModularGroupElement)message, maxNumBytes));
		}
		
		return (null);
	}
	
	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#randomArray(int, Verifier.Cryptography.PRG, byte[], int)
	 */
	@Override
	public ModularGroupElement[] randomArray(int arraySize, PRG pseudoGenerator, byte[] seed, int error) {
		// calculate the number of bits representing the containing group's order
		int containingGroupBitLength = containerGroupOrder.bitLength();
		BigInteger element = null;
		// calculate the exponent to use in order to create all the objects in the array
		BigInteger exponent = containerGroupOrder.subtract(BigInteger.ONE).divide(groupOrder);
		// calculate the number of bits per base in the random bits array returned from the PRG
		int numBitsPerNumber = 8 * (int)Math.ceil((containingGroupBitLength + error)/ 8.0);
		int firstBit = 0, lastBit = numBitsPerNumber - 1;
		// calculate the maximal base that can be generated
		BigInteger maxBase = BigInteger.valueOf(2).pow(containingGroupBitLength + error);
		
		// create the random array
		ModularGroupElement[] resultArray = new ModularGroupElement[arraySize];
		try {
			for (int i = 0 ; i < arraySize;i++) {
				// get a random base
				byte[] randNumArr = pseudoGenerator.BuildingRandom(seed, firstBit, lastBit);
				// add a zero byte at the start to convert the bits into a non-negative number
				byte[] numArr = new byte[randNumArr.length + 1];
				System.arraycopy(randNumArr, 0, numArr, 1, randNumArr.length);
				// need to clear enough bits to get a clean first byte for some reason
				numArr[1] = (byte)(numArr[1] & ~(0xFF << ((containingGroupBitLength + error) % 8)));
				BigInteger randomBase = new BigInteger(numArr);
				// normalize this base
				randomBase = randomBase.mod(maxBase);
				// calculate base^exponent mod containing group's order
				element = randomBase.modPow(exponent, containerGroupOrder);
				// add the new modular group element to the array
				resultArray[i] = new ModularGroupElement(element, this);
				// now, advance the output bits indexes
				firstBit += numBitsPerNumber;
				lastBit += numBitsPerNumber;
			}
		} catch (Exception e) {
			// shouldn't happen - the element should be inside the group
			return (new ModularGroupElement[0]);
		}
		
		return (resultArray);
	}

	/* (non-Javadoc)
	 * @see Verifier.ArithmeticSystem.Group#getGroupIdentityElement()
	 */
	@Override
	public GroupElement getGroupIdentityElement() {
		try {
			return (new ModularGroupElement(BigInteger.ONE, this));
		} catch (Exception e) {
			// this should never happened - we are the group which created the object
			return (null);
		}
	}
}
